#include <iostream>
#include <vector>
#include <algorithm>
#include <sys/time.h>
#include <cmath>
using namespace std;





vector<int> searchRange(vector<int>& nums, int target) 
{
  //vector<int> ret;
  int low=0;
  int high = nums.size()-1;
  vector<int> ret(2,-1);

  if(nums[low]>target || nums[high]<target )
    return ret;

  int i=0;
  int j=high;
  const  int mj=high;

  const int iterMax = log2(high+1)+1;

  int iter = iterMax;
  while( iter-- )
  {
    if( nums[i] < target )
    {
      low = i;
      i = (low + high + 1)/2;
    }
    else if( nums[i] == target )
    {
      if( (i==0) || ( i>0 && nums[i-1]!=target ) )
      {
        low = i;
        ret[0] = low;
        break;
      }
      else
      {
        i = (low + i)/2;
      }
    }
    else 
    {
       i = (low + i)/2;
    }

   if(low == i)
      break;
  }

  iter = iterMax;

   while( iter-- )
  {
    if( nums[j] > target )
    {
      high = j;
      j = (low + high )/2;
    }
    else if( nums[j] == target )
    {
      if( ( j==nums.size()-1 ) || ( ( j<(nums.size()-1) ) && nums[j+1]!=target ) )
      {
        high = j;
        ret[1] = high;
        break;
      }
      else
      {
        j = (high + mj+1)/2;
      }
    }
    else 
    {
       j = (high + mj+1)/2;
    }

     if( low == high)
      break;
  }

  return ret;
}

int main(int argc,char *argv[])
{
  vector<int> nums={5,7,7,8,8,10};
  int target = 6;

  struct  timeval    tv1,tv2;
  struct  timezone   tz;
  int time1 = gettimeofday(&tv1,&tz);

  //func();
  vector<int> ret = searchRange(nums,target);


  int time2 = gettimeofday(&tv2,&tz);
  cout << "time consuming:" << tv2.tv_usec - tv1.tv_usec <<"us"<< endl;

  cout<<"ret:"<<ret[0]<<","<<ret[1]<<endl;

  return 0;
}
